1. Field of the Invention
This invention relates to the field of computer architecture. Specifically, this invention is a method, apparatus and computer program product for reducing overflow and underflow exception traps resulting from the use of a stack file.
2. Background
Some computer architectures include a windowed register file (the register window file) that contains a set of registers. A register window is a selection of registers that are available to a program at a particular moment. Register windows are used to improve performance of subroutine calls (among other reasons). The SPARC.RTM. architecture is an example of a computer architecture that uses a register window file.
A register window file is one example of a stack file. A "stack file" consists of a stack structure that is partially stored in memory and partially stored in a register file for faster access. The "top-of-stack cache" refers to the registers of the stack file. Stack elements are moved from the registers to memory and back again based on stack underflow and overflow exception traps.
Generally, on entering a subroutine, the subroutine invokes a "save" instruction (or similar instruction). The "save" instruction provides the subroutine with a new register window. If the register window file does not contain enough registers to hold the new register window, the "save" instruction causes an overflow trap. When the register window file overflows, the registers in at least one older register window in the register window file must be saved (spilled) to memory to release registers for a new register window. In a similar manner the register window file underflows when register window file is empty and the computer executes an instruction (such as a "restore" instruction) to restore a previously saved register window.
In both of these circumstances, the computer generates a register window exception trap. This stack exception trap invokes a trap handler that executes instructions to handle the exception. For a register window overflow condition, the contents of one or more existing register windows are spilled (saved) to memory. For a register window underflow condition, the previously saved contents of one or more register windows are restored to the stack file (a fill).
Prior art operating systems spill and fill a fixed number of register windows at each register window exception trap (often the trap only affects a single register window). This is inefficient when there are deeply nested or recursive subroutine calls. Historically, a single fill or spill was considered appropriate because most traditional programming methodologies did not generate deep subroutine call chains. Modern programming methodologies (in particular object-oriented programs, and programs that use recursion) often generate deep call chains. For these programming methodologies, window exceptions would be reduced if more than one spill/fill occurred on a register window exception trap. However, the program mix on most computer systems includes some programs that use the traditional methodology and other programs that use the modern methodology. In addition, a single program often includes both methodologies. Thus, simply spilling or filling a fixed number of register windows does not improve the overall system efficiency.
The register window file is but one example of the use of a "top-of-stack cache." Another example is illustrated by the Intel.RTM. floating point unit (FPU) architecture. Yet another example is the hardware stack provided by a stack oriented computer architecture (such as a Forth Computer). Still another example is a return address top-of-stack cache (such as those used in some Forth computer architectures). Each of these hardware stacks are a form of a "top-of-stack cache" in that the top of the stack can be maintained in registers directly accessible by the CPU and the rest of the stack can be maintained in memory and that each stack can invoke an overflow trap or an underflow trap.
It would be advantageous to provide a spill/fill handler for top-of-stack caches that adapt to the characteristics of the currently executing program. This adaptation would improve the efficiency of the computer system by reducing the number of top-of-stack cache exceptions generated by the executing program.